/**
 * Created With IntelliJ IDEA
 * Description:牛客网: CC36 不同的子序列
 * <a href="https://www.nowcoder.com/practice/ed2923e49d3d495f8321aa46ade9f873?tpId=46&tqId=29065&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking">...</a>
 * User: DELL
 * Data: 2023-04-30
 * Time: 22:56
 */
public class Solution {
    /**
     *　解题思路（动态规划）
     * 状态定义: dp[i][j] = S的前 i 个字符的子序列和T的前 j 个字符相等的子序列数量
     * 状态转移: 当S的第 i 个字符和T的第 j 个字符相等时:
     *          dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
     *          当S的第 i 个字符和T的第 j 个字符不相等时:
     *          dp[i][j] = dp[i-1][j]
     * 初始化: 初始化数组的第一行为 0, 数组的第一列为 1,注意dp[0][0] = 1;
     * 返回值: 返回右下角的值即可
     * @param S string字符串
     * @param T string字符串
     * @return int整型
     */
    public int numDistinct (String S, String T) {
        //检查合法性
        if (S == null || T == null || S.length() < T.length()) {
            return 0;
        }
        //状态数组
        int[][] dp = new int[S.length()+1][T.length()+1];
        //初始化
        for (int i = 0; i <= S.length(); i++) {
            dp[i][0] = 1;
        }
        //状态转移
        for (int i = 1; i <= S.length(); i++) {
            for (int j = 1; j <= T.length(); j++) {
                if (S.charAt(i-1) == T.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[S.length()][T.length()];
    }

    /**
     * 解法的改进版
     * 主要是针对上面解法的空间复杂度进行优化
     * 在我们的转移方程中我们很容易得到每一次转台的转移只和 dp数组的前一列左边的值有关,
     * 因此我们的dp数组可以变成一维数组,对其遍历S.length()次,每次从右往左遍历即可.
     * @param S
     * @param T
     * @return
     */
    public int numDistinct2 (String S, String T) {
        //检查合法性
        if (S == null || T == null || S.length() < T.length()) {
            return 0;
        }
        //状态数组
        int[] dp = new int[T.length()+1];
        //初始化
        dp[0] = 1;
        //状态转移
        for (int i = 1; i <= S.length(); i++) {
            for (int j = T.length(); j >= 1; j--) {
                if (S.charAt(i-1) == T.charAt(j-1)) {
                    dp[j] += dp[j-1];
                }
            }
        }
        return dp[T.length()];
    }
}